package com.cong._37;

import java.text.ParseException;
import java.util.*;

public class Solution {
    private char[][] board;
    private Set<Character>[][] allowable = new Set[9][9];
    public void solveSudoku(char[][] board) {
        this.board = board;
        initAllowable();
        if (!recurSetNum(0)) {
            System.out.println("failed");
        }

    }

    private boolean recurSetNum(int index) {
        int i = index / 9;
        int j = index % 9;
//        if (i == 6 && j == 8) {
//            for(char[] cs: board) {
//                System.out.println(Arrays.toString(cs));
//            }
//            System.out.println("================");
//        }
        if (board[i][j] != '.') { // 这个位置填写过了
            return index == 80 || recurSetNum(index + 1);
        }
        Set<Character> charsToSet = allowable[i][j];
        if (charsToSet.size() == 0){ // 无法填写了
            return false;
        }

        for (Character c: allowable[i][j]) {
            // 填入一个char 并更新allowable
            List<Pair> p = setOneChar(i, j, c);
            if (index == 80) {
                return true;
            }/*填满了*/
            // 没有填满则继续填写下个格子
            boolean recurSet = recurSetNum(index + 1);
            if (recurSet) {
                return true;
            }/*填写成功*/

            //  下一个空格无法填写正确答案，则撤销对allowable的更新
            allowChar(c, p);
            board[i][j] = '.';
        }
        return false;
    }
    private List<Pair> setOneChar(int i, int j, char c) {
        board[i][j] = c;
        List<Pair> r = new LinkedList<>();
        for(int row = i + 1;row < 9;row++) {
            if (allowable[row][j].remove(c)) r.add(new Pair(row, j));
        }
        for(int col = j + 1;col < 9;col++) {
            if (allowable[i][col].remove(c)) r.add(new Pair(i, col));
        }
        return r;
    }
    private void allowChar(char c, List<Pair> pairs) {
        for(Pair p: pairs) {
//            System.out.printf("[%d, %d]: %c\n", p.i, p.j, c);
            allowable[p.i][p.j].add(c);
        }
    }
    private void initAllowable() {
        // 所有位置全部可以填写
        for(int i = 0;i < 9;i++) {
            allowable[i] = new Set[9];
            for(int j = 0;j < 9;j++) {
                allowable[i][j] = new HashSet<Character>();
                for(char c = '1';c <= '9';c++) {
                    allowable[i][j].add(c);
                }
            }
        }
        // 设置初始board
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if (board[i][j] != '.') {
                    for(int row = 0;row < 9;row++) {
                        allowable[row][j].remove(board[i][j]);
                    }
                    for(int col = 0;col < 9;col++) {
                        allowable[i][col].remove(board[i][j]);
                    }
                    if (i == 1 && j == 8) {
                        System.out.println("???");
                        System.out.println(Arrays.deepToString(board));
                    }
                }
            }
        }

    }

    private static class Pair {
        int i;
        int j;
        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}